package com.hsc.offer;



/**
 * @author
 * @date 2025-06-24
 * @Description 17.输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */
public class OfferTest12 {
    public static void main(String[] args) {

    }


    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        // 任意一个为空树 则都不是子结构
        if (root1 == null || root2 == null) {
            return false;
        }
        // 如果传入的两个树相同 则直接返回 true
        if (root1 == root2) {
            return true;
        }

        // 判断是否相同子结构
        // 判断当前节点是否相同
        // 情况一：isSame(root1, root2) 这种情况说明 是根节点相同的情况 进行比较
        // 但是传入的B 二叉树 不一定就是根节点 相同的情况 ，可能是 根 A树的二叉树子树比较的情况
        // 情况二：isSame(root1.left, root2) : 让root 2这个子树跟root1 的左子树开始比
        // 情况三：isSame(root1.right, root2); 让root2 跟root1 这个子树额右子树开始比
        return isSame(root1, root2) || isSame(root1.left, root2) || isSame(root1.right, root2);


    }

    /**
     * 比较的过程
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean isSame(TreeNode root1, TreeNode root2) {
        // 判断root2 子树是否为null 如果为null  说明比完了 root2
        // root 2 为子树 说明root2的树节点比root1 节点少
        if (root2 == null) {
            // 为null 数目比完了，并且说明root2的树节点比root1 节点少
            return true;
        }

        // 严谨性判断  如果 root1 ==null 直接返回false
        if (root1 == null) {
            // 如果root1 为null 说明 root2这个子树 比 root1 这个树 节点多 ，root2 就不可能是root1的子数了
            return false;
        }

        // 判断 根据节点是否相等 再判断左右节点是否相等
        if (root1.val == root2.val) {
            // 根节点相等 判断 根节点的左节点和 右节点是否相等 递归判断
            return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
        } else {
            // 根节点不相等 直接返回false
            return false;
        }


    }
}

/**
 * 树节点
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

